package com.asia.algorithmcode.linkedList;

import java.util.HashMap;
import java.util.Map;

/**
 * 138、随机链表的复制
 */
public class CopyRandomList {

    public static void main(String[] args) {
        Node node_7 = new Node(7);
        Node node_13 = new Node(13);
        Node node_11 = new Node(11);
        Node node_10 = new Node(10);
        Node node_1 = new Node(1);

        node_7.next = node_13;
        node_13.next = node_11;
        node_11.next = node_10;
        node_10.next = node_1;
        node_1.next = null;

        node_7.random = null;
        node_13.random = node_7;
        node_11.random = node_1;
        node_10.random = node_11;
        node_1.random = node_7;

        Node node = new CopyRandomList().copyRandomList(node_7);

        System.out.println(node);

    }


    public Node copyRandomList(Node head) {

        if (head == null) {
            return null;
        }

        Map<Node, Node> map = new HashMap<>();

        Node cur = head;

        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        cur = head;

        while (cur != null) {
            Node newNode = map.get(cur);
            newNode.next = map.get(cur.next);
            newNode.random = map.get(cur.random);
        }

        return map.get(head);
    }

}
